#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
#define ls (rt<<1)
#define rs (rt<<1|1)
int h[maxn], hp[maxn], ph[maxn], cnt, sz;
void heap_swap(int a, int b) {
  swap(ph[hp[a]], ph[hp[b]]);
  swap(hp[a], hp[b]);
  swap(h[a], h[b]);
}
void up(int u) {
  while(u/2 && h[u]<h[u/2]) {
    heap_swap(u, u/2);
    u >>= 1;
  }
}
void down(int rt) {
  int mn = rt;
  if(ls<=sz && h[ls]<h[mn]) mn = ls;
  if(rs<=sz && h[rs]<h[mn]) mn = rs;
  if(mn!=rt) {
    heap_swap(mn, rt);
    down(mn);
  }
}
int main() {
  int n; cin>>n;
  string op;
  while(n--) {
    cin>>op;
    if("I"==op) {
      int x; cin>>x;
      cnt++, sz++;
      h[sz] = x;
      hp[sz] = cnt, ph[cnt] = sz;
      up(sz);
    }
    else if("PM"==op) {
      cout<<h[1]<<'\n';
    }
    else if("DM"==op) {
      heap_swap(1, sz);
      sz--;
      down(1);
    }
    else if("D"==op) {
      int k; cin>>k;
      k = ph[k];
      heap_swap(k, sz);
      sz--;
      up(k);
      down(k);
    }
    else if("C"==op) {
      int k, x; cin>>k>>x;
      k = ph[k];
      h[k] = x;
      up(k);
      down(k);
    }
    else assert(false);
  }
}
